#
# @lc app=leetcode.cn id=219 lang=python3
#
# [219] 存在重复元素 II
#

# @lc code=start
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # # 我的解法
        # hashMap = {}
        # seen = set()
        # for i in range(len(nums)):
        #     if nums[i] not in seen:
        #         hashMap[nums[i]] = [i]
        #         seen.add(nums[i])
        #     else:
        #         hashMap[nums[i]].append(i)
        #     cp_idx = hashMap[nums[i]]
        #     if len(cp_idx) < 2: continue
        #     for j in range(len(cp_idx) - 1):
        #         if hashMap[nums[i]][j + 1] - hashMap[nums[i]][j] <= k:
        #             return True
        # return False

        # 滑动窗口, 大小为k
        seen = set()
        for i in range(len(nums)):
            if nums[i] in seen: return True
            seen.add(nums[i])
            # 超过窗口却没看到重复，移除窗口最前面的元素
            if len(seen) > k:
                seen.remove(nums[i - k])
        return False
# @lc code=end

